1. Field of the Invention
The present invention is directed to evaluating expressions in database management systems.
2. Background Art
Database management systems compute scalar expressions as part of their processing. There are two well-known argument evaluation approaches: lazy evaluation and eager evaluation. The lazy evaluation approach evaluates a scalar expression only when the value is needed. In contrast, eager evaluation evaluates all arguments before evaluating the expression that depends on them. Lazy evaluation avoids evaluating an expression if it is not needed, and can therefore be more efficient than eager evaluation. In contrast, eager evaluation evaluates a particular sub-expression only one time even if it is used multiple times within an expression graph. In this way, eager evaluation can alternatively evaluate a particular sub-expression fewer times than lazy evaluation would
The wasted evaluations of lazy evaluation stem from re-evaluating a sub-expression when it already has the desired value (because it has already been evaluated with the current values of its arguments). Memoization is a well known technique that can be used to avoid wasted evaluations in this case. Lazy evaluation with memoization evaluates an argument only if the value is needed and only if the value is not currently available. This gives a minimal number of evaluations for the argument. Memoization can also be applied to eager evaluation; evaluations can be saved if the argument already has been computed with the needed value. Eager evaluation with memoization will evaluate more expressions than lazy evaluation with memoization in those cases where an argument that was speculatively evaluated turns out not to be needed.
From the preceding discussion, it might appear that lazy evaluation with memoization is uniformly the best approach. This is not true: lazy evaluation with memoization minimizes the number of expression evaluations, but it does so at the expense of memoization bookkeeping that may exceed the cost of the saved evaluations. No single approach (eager or lazy, with or without memoization) is optimal in all cases. Accordingly, there is a need for a hybrid approach to expression evaluation in database management systems.